GATE PYQ

Binary Tree

Q21.
A binary tree with n>1 nodes has n_{1}, n_{2} and n_{3} nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?

Q22.
The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which. I.MBCAFHPYK II.KAMCBYPFH III.MABCKYFPH Pick the true statement from the following.

Q23.
The in-order traversal of a tree resulted in FBGADCE. Then the pre-order traversal of that tree would result in

Q24.
Consider the following C program segment where CellNode represents a node in a binary tree: struct CellNode { struct CellNOde leftChild; int element; struct CellNode rightChild; }; int GetValue(struct CellNode *ptr) { int value = 0; if (ptr != NULL) { if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL)) value = 1; else value = value + GetValue(ptr->leftChild) + GetValue(ptr->rightChild); } return(value); } The value returned by GetValue when a pointer to the root of a binary tree is passed as its argument is:

Q25.
A complete binary tree with n non-leaf nodes contains

Q26.
The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively The postorder traversal of the binary tree is:

Q27.
The maximum number of binary trees that can be formed with three unlabeled nodes is:

Q28.
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

Q29.
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of

Q30.
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. The index of the parent of elementX[i], i \neq 0, is?